/**
 * 
 */
package edu.umd.clip.lm.util;

import java.util.*;
import org.w3c.dom.*;
import java.nio.*;
import java.io.*;
import com.sleepycat.bind.tuple.*;
/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class BinaryPrefix extends XMLizable implements Comparable<BinaryPrefix>, Externalizable, Serializable {
	private static final long serialVersionUID = 1L;
	public static final String XML_ELEMENT_NAME = "binary-prefix";
	public static final String XML_ATTR_SIZE_NAME = "size";
	
	private BitSet bits;
	private short size;
	
	public BinaryPrefix() {
		this(0);
	}
	
	public BinaryPrefix(int len) {
		this(new BitSet(len), (short)len);
	}
	
	public BinaryPrefix(BitSet set, int len) {
		bits = set;
		size = (short)len;
	}
	
	public BinaryPrefix(String bitStr) {
		setBits(bitStr);
	}
	
	/**
	 * @param pref
	 * @return true if this is a prefix of @param pref
	 */
	public boolean isPrefixOf(BinaryPrefix pref) {
		if (size > pref.size) return false;
		
		BitSet test = pref.bits.get(0, size);
		test.xor(bits);
		return test.isEmpty();
	}

	/**
	 * @return the bits
	 */
	public BitSet getBits() {
		return bits;
	}

	/**
	 * @return the size
	 */
	public int getSize() {
		return size;
	}
	
	public BinaryPrefix(Element xmlnode) {
		assert(xmlnode.getTagName().equals(XML_ELEMENT_NAME));
		this.size = Short.parseShort(xmlnode.getAttribute(XML_ATTR_SIZE_NAME));
		String bitStr = xmlnode.getTextContent();
		assert(bitStr.length() == size);
		setBits(bitStr);
	}
	
	public BinaryPrefix(ObjectInput in) throws IOException, ClassNotFoundException {
		readExternal(in);
	}
	
	public BinaryPrefix(TupleInput in) throws IndexOutOfBoundsException {
		readTuple(in);
	}
	
	public void setBits(String bitStr) {
		size = (short)bitStr.length();
		this.bits = new BitSet(size);
		for(int i=0; i<size; ++i) {
			if (bitStr.charAt(i) == '1') bits.set(i);
		}		
	}
	
	public Element createXML(Document doc) {
		Element element = doc.createElement(XML_ELEMENT_NAME);
		element.setAttribute(XML_ATTR_SIZE_NAME, Integer.toString(size));
		
		element.setTextContent(toString());
		return element;
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		CharBuffer cb = CharBuffer.allocate(size);
		for(int i=0; i<size; ++i) {
			cb.put(i, bits.get(i) ? '1' : '0');
		}
		return cb.toString();
	}

	public BinaryPrefix append(boolean one) {
		BinaryPrefix newP = new BinaryPrefix((BitSet)bits.clone(), (short)(size+1));
		newP.bits.set(size, one);
		return newP;
	}
	
	public BinaryPrefix appendOne() {
		return append(true);
	}
	
	public BinaryPrefix appendZero() {
		return append(false);
	}
	
	public BinaryPrefix reverse() {
		BinaryPrefix prefix = new BinaryPrefix(size);
		for(int i=0; i<size; ++i) {
			prefix.bits.set(size-1-i, bits.get(i));
		}
		return prefix;
	}
	/* (non-Javadoc)
	 * @see edu.umd.clip.lm.util.XMLizable#getElementName()
	 */
	@Override
	public String getElementName() {
		return XML_ELEMENT_NAME;
	}

	public boolean get(int index) {
		if (index >= size || index < 0) throw new IndexOutOfBoundsException();
		return bits.get(index);
	}
	/**
	 * 
	 * @param nskip number of prefix bits to skip
	 * @return returns binary prefix consisting of (nskip+1)-th .. bits
	 */
	public BinaryPrefix getSuffix(int nskip) {
		assert(nskip <= size);
		return new BinaryPrefix(bits.get(nskip, size), (short)(size-nskip));
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Comparable#compareTo(java.lang.Object)
	 */
	public int compareTo(BinaryPrefix other) {
		int minSize = Math.min(size, other.size);
		for(int i=0; i<minSize; ++i) {
			if (bits.get(i) ^ other.bits.get(i)) {
				return (bits.get(i) ? 1 : 0) - (other.bits.get(i) ? 1 : 0);
			}
		}
		return size - other.size;
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
		if (! (obj instanceof BinaryPrefix)) return false;
		BinaryPrefix p = (BinaryPrefix) obj;
		return size == p.size && bits.equals(p.bits);
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		return bits.hashCode();
	}

	public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
		size = in.readShort();
		bits = new BitSet(size);
		if (size > 0) {
			byte bytes[] = new byte[(size+7) / 8];
			in.readFully(bytes);
			
			for(short i=0; i<size; ++i) {
				int offset = i / 8;
				int bit = i % 8;
				if ((bytes[offset] & (1 << bit)) != 0) {
					bits.set(i);
				}
			}
		}
	}

	public void writeExternal(ObjectOutput out) throws IOException {
		out.writeShort( size);
		if (size > 0) {
			byte bytes[] = new byte[(size + 7) / 8];
			for(short i=0; i<size; ++i) {
				if (get(i)) {
					int offset = i / 8;
					int bit = i % 8;
					bytes[offset] |= 1 << bit;
				}
			}
			out.write(bytes);
		}
	}

	public void readTuple(TupleInput in) throws IndexOutOfBoundsException {
		size = in.readShort();
		bits = new BitSet(size);
		if (size > 0) {
			byte bytes[] = new byte[(size+7) / 8];
			in.readFast(bytes);
			
			for(short i=0; i<size; ++i) {
				int offset = i / 8;
				int bit = i % 8;
				if ((bytes[offset] & (1 << bit)) != 0) {
					bits.set(i);
				}
			}
		}
	}

	public void writeTuple(TupleOutput out) {
		out.writeShort( size);
		if (size > 0) {
			byte bytes[] = new byte[(size + 7) / 8];
			for(short i=0; i<size; ++i) {
				if (get(i)) {
					int offset = i / 8;
					int bit = i % 8;
					bytes[offset] |= 1 << bit;
				}
			}
			out.writeFast(bytes);
		}
	}

	public static int distance(BinaryPrefix p1, BinaryPrefix p2) {
		int minLen = Math.min(p1.getSize(), p2.getSize());
		int match = 0;
		for(int i=0; i<minLen; ++i) {
			if (p1.get(i) == p2.get(i)) {
				++match;
			} else {
				break;
			}
		}
		
		return p1.getSize() + p2.getSize() - 2*match;
	}
	
	public static BinaryPrefix getCommonPrefix(BinaryPrefix p1, BinaryPrefix p2) {
		int minLen = Math.min(p1.getSize(), p2.getSize());
		int match = 0;
		for(int i=0; i<minLen; ++i) {
			if (p1.get(i) == p2.get(i)) {
				++match;
			} else {
				break;
			}
		}
		return new BinaryPrefix(p1.getBits().get(0, match), match);
	}
	
	public static void main(String args[]) {
		BinaryPrefix p1 = new BinaryPrefix("110101011");
		BinaryPrefix p2 = new BinaryPrefix("110101111");
		BinaryPrefix p3 = new BinaryPrefix("0101");
		
		System.out.printf("Common prefix of %s and %s is %s\n", p1, p2, getCommonPrefix(p1, p2));
		System.out.printf("Common prefix of %s and %s is %s\n", p1, p3, getCommonPrefix(p1, p3));
	}
}
